#include "Skinner_Cored.h"
#include "Log.h"
#include "PS_Log.h"
#include <limits>       // std::numeric_limits


Skinner_Cored::Skinner_Cored(int subset_size, int extreme_size) {
    sample_subset_size = subset_size;
    extreme_set_size   = extreme_size;
}

// This method follows the algorithm in Cantone et al's paper
// on the "Antipole Tree".  Their goal is to find a pair or
// objects that is very far apart (a pair of approximate antipoles),
// approximating the two farthest-apart pair (the true antipoles).
//
// They do it by repeatedly removing interior points.  The basic
// idea is to pick k objects at random, find their mediod, and remove
// the mediod from the set.  If you do this enough times, you'll tend
// to remove interior objects, and be left with extreme objects.
//
// They use k=3.
//
// Their algorithm is as follows:
// S = initial set
// while (|S| > threshold) {
//    X = k objects from S, at random
//    remove mediod(X) from S
// }
//
// where mediod(X) returns the object "in the middle" of X.
//
// That's not quite it, since they actually partition S into several
// disjoint subsets of size k, whereas the above pseudocode may re-use
// the same objects on consecutive passes, because, by randomly choosing the
// objects that go into each subset X, we may pick the same objects again.
// For more details, see
// "Antipole Tree Indexing to Support Range Search and K-Nearest Neighbor
//  Search in Metric Spaces",
//  by D. Cantone, A. Ferro, A. Pulvirenti, D. Reforgiato
// (it's online)
//
void Skinner_Cored::separate(Cluster *cluster) {
    LOG_ENTER(SKIN,"Skinner_Cored::separate");
    LOG(SKIN) << "sample_subset_size=" << sample_subset_size << " extreme_set_size=" << extreme_set_size;

    int n = cluster->span.n;
    // First, grab the items into an array
    LMO_Iterator iter = cluster->span.start;
    LMO_Iterator *items = new LMO_Iterator[n];
    for (int i=0; i<n; i++) {
        items[i] = iter++;
    }
    // randomize the array.
    std::random_shuffle(items, items + n);

    Log::output << "Shuffled set: (";
    for (int i=0; i<n; i++)
        Log::output << " " << (*items[i])->ID;
    Log::output << ")\n";


    // Now do Cantone et al's algorithm on the array.
    // We will just move things around the array, which will be
    // maintained in two parts, the first part has the extreme
    // objs, and the second had the interior ones.
    // Whenever we find a mediod, we swap it with end of the extreme set,
    // and shrink that set, and expand the interior set.  There's a version
    // of quicksort that does partition that way.

    int first_extreme  = 0; // last extreme is n-1, initially
    int first_interior = n; // one past the end of the array, ie initially empty

    // do several passes through the set, until we've removed enough mediods
    while (first_interior - first_extreme > extreme_set_size) {

        LOG(SKIN) << "MEDIOD-REMOVAL PASS";

        // each set X will be a different (disjoint) chunk of the array
        int chunk_start = 0;
        while (first_interior - chunk_start > extreme_set_size) {
            int chunk_end = chunk_start + sample_subset_size - 1;
            if (chunk_end > n-1) {
                chunk_end = n-1;
            }
            else if (first_interior - chunk_end - 1 < sample_subset_size) {
                // got a runt chunk at the end, absorb it
                chunk_end = first_interior - 1;
            }

            LOG(SKIN) << "chunk_start=" << chunk_start << " chunk_end=" << chunk_end;

            int i_medioid = chunk_start;
            double min_tot_dist = std::numeric_limits<int>::max();

            for (int i=chunk_start; i <= chunk_end; i++) {

                LOG(SKIN) << "chunk items[" << i << "].ID=" << (*items[i])->ID;

                double tot_dist = 0;
                for (int j=chunk_start; j <= chunk_end; j++) {
                    if (i == j) continue; // skip self distance calcs
                    tot_dist += (*items[i])->distance(*items[j]);
                }
                if (tot_dist < min_tot_dist) {
                    min_tot_dist = tot_dist;
                    i_medioid = i;
                }
            }

            LOG(SKIN) << "chunk_start=" << chunk_start << " i_medioid=" << i_medioid;
            LOG(SKIN) << "mediod ID=" << (*(items[i_medioid]))->ID;

            // got medioid.  Swap it to interior set.
            LMO_Iterator tmp        = items[i_medioid];
            items[i_medioid]        = items[first_interior-1];
            items[first_interior-1] = tmp;

            std::stringstream title;
            title << "AFTER REMOVING " << (n-first_interior)
                  << " INTERIOR POINTS FROM CLUSTER (ID " << cluster->ID << ")";
            PS_Log::show_title(title.str());

            PS_Log::print(items, n, first_extreme, first_interior-1, true);
            PS_Log::print(items, n, first_interior, n, false);
            PS_Log::ps->end_page();

            // resize sets
            first_interior--;

            Log::output << "Interior set: (";
            for (int i=first_interior; i<n; i++)
                Log::output << " " << (*items[i])->ID;
            Log::output << ")\n";

            Log::output << "Extreme set: (";
            for (int i=first_extreme; i<=first_interior-1; i++)
                Log::output << " " << (*items[i])->ID;
            Log::output << ")\n";

            Log::output << "All items: (";
            for (int i=0; i<n; i++)
                Log::output << " " << (*items[i])->ID;
            Log::output << ")\n";

            // advance to next chunk
            chunk_start = chunk_end + 1;

            LOG(SKIN) << "first_interior=" << first_interior << " chunk_start=" << chunk_start << " extreme_set_size=" << (extreme_set_size);
            LOG(SKIN) << "continue? " << ((first_interior - chunk_start > extreme_set_size) ? "yes" : "no");
        }
    }


    // and finally stuff each of the objects into one of the two lists
    cluster->interior_set.clear();
    cluster->extreme_set.clear();
    for (int i=first_extreme; i<first_interior; i++) {
        cluster->extreme_set.append(*(items[i]));
    }

    for (int i=first_interior; i<n; i++) {
        cluster->interior_set.append(*(items[i]));
    }

    delete[] items;
}
